|
![](/i/fill.gif) |
Weee... check this out:
A full scan of a table containing ten million items requires up to ten
million operations. (On average, half that.) Using binary chop, it takes
only the binary logarithm of that - about 25 operations.
If a computer can process 1,000 operations per second (bearing in mind,
comparing a record to the target being looked up is a far few machine
instructions), we achieve the following times:
Full scan: 2.777 hours
Binary chop: 0.025 seconds
So one way takes almost three hours to do a single lookup, while the
other can do 40 lookups per second. O(log N) FTW!
But wait, check this out. Perhaps you are somehow unimpressed with
taking a 3-hour operation and completing it in 1/40th of a second. Well
try this for size:
Assume there are 10^80 atoms in the observable universe. If you
sequentially full scan then all, one by one, at 1,000 atoms per second,
it'll take you 10^77 seconds.
This is longer than the universe has existed (10^11 seconds).
Hypothetically, it's longer than it will take for all the energy in the
universe to be exhausted. By the time 10^77 seconds is up, the universe
will have died a cold, dark, silent death of total equilibrium a very
long time ago.
In short, this procedure is so slow that there isn't enough time or
energy in the whole of the known universe to actually complete it. (But
then, who's going to pin a unique record to every atom in the universe
anyway?)
On the other hand, according to my sums 10^80 is roughly 2^266. Thus,
the binary chop algorithm requires only 266 operations, and can easily
complete the entire process in well under a second. [If we assume
completely random access to any atom in the universe, which completely
defies several known physical laws...]
Like, wow man!
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
![](/i/fill.gif) |